2343

Created at : 2024-03-08 11:34
2343

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
        ios::sync_with_stdio(false);
        cin.tie(nullptr);

        uint32_t n, m, MaxSize = 0, TotalSize = 0;;
        cin >> n >> m;
        vector<uint32_t> CourseSizes(n, 0);
        for(int i = 0; i < n; ++i)
        {
            cin >> CourseSizes[i];
            TotalSize += CourseSizes[i];
            MaxSize = max(MaxSize, CourseSizes[i]);
        }

        uint32_t LowSize = max(TotalSize / m, MaxSize), HighSize = TotalSize;
        
        while (LowSize <= HighSize)
        {
            uint32_t BluerayNum = 0, BlueraySize = 0;
            uint32_t Mid = (LowSize + HighSize) / 2;
            for(auto CourseSize : CourseSizes)
            {
                if(BlueraySize + CourseSize > Mid)
                {
                    ++BluerayNum;
                    BlueraySize = 0;
                }
                BlueraySize += CourseSize;
            }
            if(BlueraySize > 0) ++BluerayNum;
            if(BluerayNum <= m) HighSize = Mid - 1;
            else LowSize = Mid + 1;
        }
        cout << LowSize;
        return 0;
}

이분탐색을 숫자를 찾는 것만이 아닌 다른 것에 사용한다는 것을 처음 알았다.

유형

이분 탐색
매개 변수 탐색